/*
https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/description/
947.移除最多的同行或同列石头
方钊堉 2024.10.13
并查集
*/


class Solution {
public:
    int parent[20003]; // 并查集的父节点数组

    // 查找函数，带路径压缩优化
    int findRoot(int index) {
        if (parent[index] != index) {
            parent[index] = findRoot(parent[index]); // 路径压缩
        }
        return parent[index];
    }

    // 合并两个节点所在的集合
    void unionSets(int index1, int index2) {
        parent[findRoot(index1)] = findRoot(index2);
    }

    // 计算可以移除的最大石头数量
    int removeStones(vector<vector<int>>& stones) {
        // 初始化并查集
        for (int i = 0; i < 20003; ++i) {
            parent[i] = i;
        }

        // 合并每个石头的 x 和 y 坐标
        for (auto &stone : stones) {
            int x = stone[0];
            int y = stone[1] + 10001; // 将 y 坐标映射到 [10001, 20001) 范围内
            unionSets(x, y);
        }

        // 使用集合来存储每个连通分量的根节点
        set<int> uniqueRoots;
        for (auto &stone : stones) {
            int x = stone[0];
            uniqueRoots.insert(findRoot(x));
        }

        // 可以移除的石头数量等于总石头数减去连通分量的数量
        return stones.size() - uniqueRoots.size();
    }
};